The present invention is generally related to digital storage devices. In particular, the present invention is related to digital storage device, such as a last-in first-out buffer (LIFO), in which data is written in a first sequence and read out in a second sequence that is transposed from the first sequence.
A first-in-first-out (FIFO) device requires that data be stored and then read out in the sequence in which it was stored. A FIFO can be utilized to provide a video line delay in digital image processing circuitry, as the first value read out from the FIFO is obtained only after all of the data has been sequentially stored in the FIFO. For example, a full video line delay is provided if the number of storage locations in the FIFO is matched to the number of pixels to be stored from the video line. Data representative of a first pixel is not retrieved from the FIFO until the data for the last pixel has been stored in the FIFO resulting in a one line delay.
The most common architecture of a FIFO is that of a shift-register which shifts data from one register to the next until the data is output after traveling the length of the FIFO. Shift-registers, however, require a good deal of chip space and power, especially when employed in digital image processing applications where the line length may require between 570 to 768 storage locations. Another disadvantage of a shift-register FIFO is that variable or programmable line lengths are not practically feasible, as the output of all the registers would have to be multiplexed to the output of the FIFO.
A better approach to a FIFO architecture is illustrated in copending application entitled "Memory Based Line-Delay Architecture", U.S. application Ser. No. 07/488,824, filed concurrently with the present application, which discloses a memory based line delay architecture that employs a pointer unit to sequentially address a plurality of word storage locations in a storage unit. The pointer unit is composed of one bit shift registers that shift a "travelling 1" along the length of the pointer unit to address read enable and write enable lines coupled to the word storage locations. The one bit shift registers are resettable to permit the length of the line delay to be varied. The FIFO architecture requires a minimum of chip space, has low power requirements, is programmable in length, and is flexible to permit changes in aspect ratio.
In some situations, it is desirable to retrieve information from a storage device in a sequence that is transposed from the sequence in which data was stored in the storage device, namely, in a LIFO mode of operation starting with the last word of data that was stored and progressing to the first word of data that was stored. The architecture disclosed in the above-described copending application, however, is limited to a FIFO mode of operation. Thus, it would be desirable to provide a device architecture having the advantages of the FIFO architecture described above that could also be used in a transpose mode of operation, and in particular in a LIFO mode of operation.